// run: $exec < input
// opt: 0
// flag: -g
#include <iostream>
#include <cstring>

long long inf  = (1ll) << 44;
int const maxn = 4010;
long long a[maxn][2];
long long f[maxn][2];
long long sum[maxn][2], sum1[maxn][2];
long long rsum[maxn][2], rsum1[maxn][2];
int n, m;

long long calc(int l, int r, int c, int op)
{
	if (l > r) return 0;
	if (l == r) return a[l][c];
	if (op == 0) {
		int len = (r - l + 1);
		return calc(l + (len + 1) / 2, r, c, 2) + calc(l, l + (len + 1) / 2 - 1, c, 1);
	} else if (op == 2) { // all up
		auto tmp = rsum1[l][c] - rsum1[r + 1][c];
		tmp -= (sum[r][c] - sum[l - 1][c]) * (n - r);
		return tmp;
	} else { // all down
		auto tmp = sum1[r][c] - sum1[l - 1][c];
		tmp -= (sum[r][c] - sum[l - 1][c]) * (l - 1);
		return tmp;
	}
}

long long dfs(int x, int co)
{
	if (x > n) return 0;
	if (f[x][co] < inf) return f[x][co];
	for (int i = 1; x + i - 1 <= n; i++) {
		for (int all = 0; all < 2; all++) {
			long long cost = 0;
			if (x + i - 1 != n) {
				if (co == !all) cost = calc(x, x + i - 1, !all, 0);
				else if (co == all) cost = calc(x - 1, x + i - 1, !all, 0) - a[x - 1][!all];
				else cost = calc(x, x + i - 1, !all, 2);
			} else {
				if (co == !all) cost = calc(x, x + i - 1, !all, 1);
				else if (co == all) cost = calc(x - 1, x + i - 1, !all, 1) - a[x - 1][!all];
			}

			if (x + i - 1 != n) cost += a[x + i][all];
			if (co == 2 && x + i - 1 == n) continue;
			f[x][co] = std::min(f[x][co], cost + dfs(x + i + 1, !all));
		}
	}
	return f[x][co];
}

void init_sum()
{
	for (int i = 1; i <= n; i++)
		for (int c = 0; c < 2; c++) {
			sum[i][c] = sum[i - 1][c] + a[i][c];
			sum1[i][c] = sum1[i - 1][c] + a[i][c] * i;
		}
	for (int i = n; i >= 1; i--)
		for (int c = 0; c < 2; c++) {
			rsum[i][c] = rsum[i + 1][c] + a[i][c];
			rsum1[i][c] = rsum1[i + 1][c] + a[i][c] * (n - i + 1);
		}
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	for (int ti = 1; ti <= T; ti++) {
		std::cout << "Case #" << ti << ": ";
		std::cin >> n;
		for (int i = 0; i <= n; i++) f[i][0] = f[i][1] = inf;

		for (int i = 1; i <= n; i++) std::cin >> a[i][0] >> a[i][1];
		init_sum();

//		std::cout << calc(1, 2, 0, 2) << "\n"; return 0;

		std::cout << dfs(1, 2) << "\n";
	}
}

